package DemoText;
/**
 * 排序数组 分三块 O(nlogn)
 */

import java.util.Random;

public class LeetCode912 {
    public int[] sortArray(int[] nums) {
        partition(nums, 0, nums.length - 1);
        return nums;
    }
    public void partition(int[] nums, int left, int right) {
        if (left >= right) return;
        Random random = new Random();
        int l = left - 1, r = right + 1;
        int n = right - left + 1;
        int target = nums[random.nextInt(n) + left];
        int i = left;
        while (i < r) {
            if (nums[i] > target) swap(nums, --r, i);
            else if (nums[i] < target) swap(nums, ++l, i++);
            else i++;
        }
        partition(nums, left, l);
        partition(nums, r, right);
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
